package DoblePointer;//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
//
// 示例: 
//
// 输入: [0,1,0,3,12]
//输出: [1,3,12,0,0] 
//
// 说明: 
//
// 
// 必须在原数组上操作，不能拷贝额外的数组。 
// 尽量减少操作次数。 
// 
// Related Topics 数组 双指针 👍 1263 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class moveZeroes {
    public void moveZeroes1(int[] nums) {
        /**1 双指针笨方法
         首先slow找到第一次出现0的位置，如果找不到，则说明没有0无需后续操作
         然后计算出现0的次数
         然后fast指针开始找不为0的值，如果找到时是在slow指针的后面，则交换slow和fast的值，同时二者后移
         最终将 后面的值归为0
         */
         int n = nums.length;
         int fast = 0;
         int slow = 0;
         int v = 0;


         //首先slow先移动到第一个0的位置
         while(slow<n&&nums[slow]!=0){
             slow++;
         }
         if(slow==n)
             return;
         for(int num:nums){
             if(num==0)
                 v++;
         }
         int i = 0;
         while(fast<n){
             while(fast<n && nums[fast]==0){
                 fast++;
             }
             if(fast>slow&&fast<n){
                 i++;
                 nums[slow++] = nums[fast++];
             }else{
                 fast++;
             }
         }
         if(i==0)
             return;
         for(int j = n-v;j<n;j++){
             nums[j]=0;
         }
    }

    public void moveZeroes(int[] nums) {
        //2 直接进行交换，一次遍历，如果当前值为0，则交换后面的值，否则向后移
        // 并且保证交换后再次检查
        int n = nums.length;
        int i = 0, j = 0;
        while (j < n) {
            if (nums[j] == 0) {
                j++;
                continue;
            }
            nums[i++] = nums[j++];
        }
        for (int k = i; k < n; k++) {
            nums[k]=0;
        }
    }



}
//leetcode submit region end(Prohibit modification and deletion)
